package dynamic_programming.intervalDP;

import java.util.Arrays;

/**
 * 戳气球 - 312
 */
public class 戳气球 {
    public static void main(String[] args) {
        int[] nums = {3, 1, 5, 8};
        int res = new 戳气球().maxCoins(nums);
        System.out.println(res);
    }

    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n + 2];
        int[][] cache = new int[n + 2][n + 2];

        System.arraycopy(nums, 0, arr, 1, n + 1 - 1);
        arr[0] = arr[n + 1] = 1;

        for (int[] ints : cache) {
            Arrays.fill(ints, -1);
        }

        return dfs(arr, cache, 0, arr.length - 1);
    }

    private int dfs(int[] arr, int[][] cache, int left, int right) {
        if (left >= right - 1) {
            return 0;
        }
        if (cache[left][right] != -1) {
            return cache[left][right];
        }

        for (int i = left + 1; i < right; i++) {
            int sum = arr[left] * arr[i] * arr[right];
            int l = dfs(arr, cache, left, i);
            int r = dfs(arr, cache, i, right);
            sum += l + r;
            cache[left][right] = Math.max(cache[left][right], sum);
        }


        return cache[left][right];
    }
}
